import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.stream.Stream;

/**
 * 反转链表
 * 题目：反转一个单链表。
 * <p>
 * 示例:
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * <p>
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 * <p>
 * 来源：力扣（LeetCode-206）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list
 *
 * @author godfrey
 * @since 2020-12-04
 */
@DisplayName("反转链表")
public class ReverseList extends BaseTest {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments(
                        new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))))));
    }

    @DisplayName("迭代法-时间复杂度O(n)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void reverseList(ListNode head) {
        if (head == null || head.next == null) {
            System.out.println(head);
            return;
        }
        //申请节点，pre和 cur，pre指向null
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while (cur != null) {
            //记录当前节点的下一个节点
            tmp = cur.next;
            //然后将当前节点指向pre
            cur.next = pre;
            //pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        System.out.println(pre);
    }
}